---
title: "双子数"
created: 2025-11-28
tags:
  - 算法
---

# 双子数

## 题目 [双子数](https://www.lanqiao.cn/paper/4103/problem/17105/)

![[image-a48780e0.png]]

## 思路分析

想法是先筛出要用的素数 再来个二重循环枚举

要用的素数大概有多少个  直接23333333333333‬显然是不可能的

$x=p^2\times q^2$，所以最大的 $p$ 和 $q$ 应该满足
$p^2\times q^2\le 23333333333333$

考虑到最小化的情况，即 $p=q$ 时取 $x$ 的最大值 $p^4=23333333333333$

直接取 $\sqrt{23333333333333}=4,830,458$

另外 考虑到long long可能也溢出 将int 替换成 \_\_int128

那么涉及输入输出就别用int128了 不然得重新写print函数

要输出的cnt 用long long 就行

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

#define int __int128
const int N=4830458;
typedef long long LL;
bool st[N];
vector<int> primes;
void get_primes(){
	for(int i=2;i<=N;i++){
		if(!st[i]){
			primes.push_back(i);
			for(int j=i;j<=N;j+=i)
				st[j]=true;
			}
	}
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	get_primes();
	LL cnt=0;
	for (int i = 0; i < primes.size(); i++) {
        for (int j = i + 1; j < primes.size(); j++) {
            int p = primes[i], q = primes[j];
            int product = p * p * q * q;
            if (product < 2333) continue;
            if (product > 23333333333333) break;
            cnt++;
        }
    }
	cout<<cnt;
	return 0;
 }
```

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

// 2333,23333333333333  sqrt一下：4830458.9153964450212949209345558 筛出这个范围的素数就差不多了
#define int __int128
typedef long long LL;
const int N=4830458;
bool st[N];
int primes[N],cnt;
void get_prime(){
	for(int i=2;i<=N;i++){
		if(!st[i])
			primes[cnt++]=i;{
			for(int j=i;j<=N;j+=i)
				st[j]=true;
			}
	}
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	get_prime();
	LL res=0;
	for(int i=0;i<cnt;i++){
		for(int j=i+1;j<cnt;j++){
			int p=primes[i],q=primes[j];
			int tmp=p*p*q*q;
			if(tmp<2333)	continue;
			if(tmp>23333333333333) break;
			res++;
		}
	}
	cout<<res<<endl;
	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[子2023|子2023]] 🏠 [[00-冲刺国赛]] ➡️ [[班级活动|班级活动]]